package Year22_Month06.day18;

public class 从前序与中序遍历序列构造二叉树 {
    int index;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        //遍历二叉树的递归过程是根据中序遍历来进行子树的区分的
        int n = preorder.length;
        return rebuildTree(preorder,inorder,0,n);
    }

    public TreeNode rebuildTree(int[] preorder,int[] inorder,int inleft,int inright){
        if(index == preorder.length || inleft >= inright) return null;

        //准备开始寻找当前树根节点在中序遍历数组中的位置，为后续的递归做准备
        int pos = inleft;
        while(pos < inright){
            if(inorder[pos] == preorder[index]) break;
            pos++;
        }
        //找到了之后就开始准备构造二叉树
        int nodeVal = preorder[index];
        index++;//当前树根节点被构造之后，前序遍历数组中的元素就要往后移一位
        TreeNode root = new TreeNode(nodeVal);
        root.left = rebuildTree(preorder,inorder,inleft,pos);
        root.right = rebuildTree(preorder,inorder,pos+1,inright);
        return root;
    }
}
